package year2024.month4;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class MaxProfit {

    /**
     * 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
     */
    @Test
    void test1(){
        Assertions.assertEquals(2,maxProfit(2, new int[]{2,4,1}));
    }

    /**
     * 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出,
     * 这笔交易所能获得利润 = 6-2 = 4 。
     *
     * 随后，在第 5 天 (股票价格 = 0) 的时候买入，
     * 在第 6 天 (股票价格 = 3) 的时候卖出,
     * 这笔交易所能获得利润 = 3-0 = 3
     */
    @Test
    void test2(){
        Assertions.assertEquals(7,maxProfit(2, new int[]{3,2,6,5,0,3}));
    }

    @Test
    void test3(){
        Assertions.assertEquals(13,maxProfit(2,new int[]{1,2,4,2,5,7,2,4,9,0}));
    }

    /**
     * 188 买卖股票的最佳时机
     * 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
     *
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
     *
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {


        this.prices=prices;
        /**
         * 第二维数组的索引对应 k-1
         */
        dayKMaxProfit = new int[prices.length][k];
        for (int[] ints : dayKMaxProfit) {
            Arrays.fill(ints,-1);
        }

        return profit(0,k);

    }

    int[] prices;
    int[][] dayKMaxProfit;

    int profit( int startPosition, int k){

        String prefix = "在第" + (startPosition+1) + "天，还剩" + k + "次交易次数的最大利润是：";


        if(startPosition>=prices.length){
            return 0;
        }

        if(k==0){
            // 超过限制交易次数，不能再卖股票了
            System.out.println(prefix+0);
            return 0;
        }

        int cachedProfit = -1;
        if(startPosition!=-1) {
            cachedProfit=dayKMaxProfit[startPosition][k - 1];
        }
        if(cachedProfit!=-1){
            System.out.println("缓存命中，"+prefix+cachedProfit);
            return cachedProfit;
        }

        int max =0;

        for (int i = startPosition; i < prices.length; i++) {

            // 此刻立即卖掉能获利多少，如果 i == startPosition 那么就代表这时不卖出也不买入
            int currentProfit =0;

            // 还剩下的交易次数
            int kRemain ;

            if(i == startPosition){
                // 本次既不卖出也不买入，所以不消耗交易次数
                kRemain = k;
            }else {
                // 因为此次进行了卖出操作，所以消耗了交易次数
                kRemain = k-1;

                currentProfit =  prices[i] - prices[startPosition];
            }

            int p2 = profit( i+1,kRemain);
            // 不卖的话就进入下一个循环

            max = Math.max(max,currentProfit+p2);
        }
        System.out.println(prefix+max);
        return dayKMaxProfit[startPosition][k-1]=max;
    }
}
